"""
author: tangliqi
date: 2021/9/16 9:56 上午
desc: None
      ┌─┐       ┌─┐
   ┌──┘ ┴───────┘ ┴──┐
   │                 │
   │       ───       │
   │  ─┬┘       └┬─  │
   │                 │
   │       ─┴─       │
   │                 │
   └───┐         ┌───┘
       │         │
       │         │
       │         │
       │         └──────────────┐
       │                        │
       │                        ├─┐
       │                        ┌─┘
       │                        │
       └─┐  ┐  ┌───────┬──┐  ┌──┘
         │ ─┤ ─┤       │ ─┤ ─┤
         └──┴──┘       └──┴──┘
                神兽保佑
               代码无BUG!

    binary_search: 二分查找
"""


def b_search(search_array, search_val):
    """
    不带边界搜索的二分查找
    :param search_array: 待搜索数组
    :param search_val: 查找值
    :return:
    """
    array_len = len(search_array)
    low = 0
    high = array_len - 1
    count = 0
    while low <= high:
        # mid = (low + high) // 2
        mid = low + (high - low) // 2  # 为了防止数字溢出，写成这种形式
        count += 1

        if search_array[mid] == search_val:
            return mid, count
        elif search_array[mid] < search_val:
            low = mid + 1
        else:
            high = mid - 1
    return "该值不存在数组中"


array = [1, 4, 7, 9, 16, 28, 31, 56, 89, 101, 230, 236, 251, 254]
print(b_search(array, 15))
print(b_search(array, 17))
print(b_search(array, 89))
print(b_search(array, 7))
